sup-extra CodeForces-600E Lomsat gelral 启发式合并

Posted at 2019-01-20 ICPC 

CodeForces-600E Lomsat gelral 启发式合并

---

题意就是将一棵树的节点涂色，数目最多的颜色就是主导色，然后要求输出每一个点的主导色，如果有多个主导色就输出主导色的和。

解法参考了他人代码，具体思路即首先存储每个子树的颜色，然后再按照颜色出现次数维护sum，再存储最大次数的sum值。由于是树所以遍历回去之后不用考虑子树的状态，可以放心地调换color和sum。调换之后就能保证是将少的一组值合并到多的一组值里面去，即启发式合并的思想。

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <map>
#define maxl 100005
using namespace std;
int n;
map<int,int> color[maxl];
//color[x][y]:x= vertex number,y=color,val=color-sum;
map<int,long long >sum[maxl];
//sum[x][y]:x=vertex number,y=color-sum,val=res;
vector<int> tree[maxl];
long long res[maxl];
void dfs(int s,int e)
{
    for(int i=0;i<tree[s].size();i++)
    {
        int v=tree[s][i];
        if(v==e) continue;
        dfs(v,s);
        if(color[s].size()<color[v].size())
        {
            swap(color[s],color[v]);
            swap(sum[s],sum[v]);
        }
        for(map<int,int>::iterator it=color[v].begin();it!=color[v].end();it++)
        {
            sum[s][color[s][it->first]]-=it->first;//sub color
            color[s][it->first]+=it->second;//change color-sum
            sum[s][color[s][it->first]]+=it->first;//add color
        }
    }

    res[s]=sum[s].rbegin()->second;
}
int main(void)
{
    while(~scanf("%d",&n))
    {
        int c;
        for(int i=1;i<=n;i++)
        {
            tree[i].clear();
            color[i].clear();
            sum[i].clear();
        }

        for(int i=1;i<=n;i++)
        {
            scanf("%d",&c);
            color[i][c]=1;
            sum[i][1]=c;
        }
        for(int i=1;i<n;i++)
        {
            int a,b;
            scanf("%d%d",&a,&b);
            tree[a].push_back(b);
            tree[b].push_back(a);
        }
        dfs(1,0);
        for(int i=1;i<n;i++)
            printf("%lld ",res[i]);
        printf("%lld\n",res[n]);
    }
	return 0;
}